946E - Largest Beautiful Number - CodeForces Solution

// Hydro submission #[email protected]
#include<bits/stdc++.h>
using namespace std;

char s[200010];
int n;
int num[200010][10];

void solve(){
	for(int i=n;i>=1;i--){
		for(int j=s[i]-'1';j>=0;j--){
			if(i==1&&j==0) continue;
			int x=0;
			for(int k=0;k<10;k++) x+=num[i-1][k]^(k==j);
			if(x<=n-i){
				for(int k=1;k<i;k++) putchar(s[k]);
				putchar(j+'0');
				for(int k=i+1;k<=n-x;k++) putchar('9');
				for(int k=9;k>=0;k--){
					if(num[i-1][k]^(j==k)) putchar(k+'0');
				}
				puts("");
				return;
			}
		}
	}
	for(int i=1;i<=n-2;i++) putchar('9');
	puts("");
}


int main(){
	int t;cin>>t;
	while(t--){
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=1;i<=n;i++){
			int ii=s[i]-'0';
			for(int k=0;k<10;k++){
				num[i][k]=num[i-1][k]^(ii==k);
			}
		}
		solve();
	}
	
	return 0;
}